#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
/*
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]
*/

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define SOL_SIZE 2

int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{
    int *res = (int *)malloc(SOL_SIZE * sizeof(int));
    for (int i = 0; i < numsSize; i ++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] + nums[j] == target) {
                res[0] = i;
                res[1] = j;
                *returnSize = 2;
                return res;
            }
        }
    }

    *returnSize = 0;
    return res;
}

struct vat
{
    int value; //保存数值
    int  id;   //保存在数组中位置
};

int compVatFunc(void* a, void* b)
{
    struct vat* node1 = (struct vat*)a;
    struct vat* node2 = (struct vat*)b;
    return node1->value - node2->value;
}

int* qtwoSum(int* nums, int numsSize, int target, int* returnSize)
{
    struct vat * numsVat = (struct vat *)malloc((sizeof(struct vat)) * numsSize);
    *returnSize = 2;
    int *returnSum   = (int*)malloc((sizeof(int)) * 2);
    int i;


    //装桶
    for(i =0; i <numsSize ;i++)
    {
        numsVat[i].value = nums[i];
        numsVat[i].id    = i;
    }
    //快速排序
    qsort(numsVat,numsSize,sizeof(struct vat),compVatFunc);
    //双指针
    int indexLeft = 0;
    int indexRight = numsSize - 1;
    while(indexLeft < indexRight)
    {
        if( target == (numsVat[indexLeft].value + numsVat[indexRight].value)) 
        {
            returnSum[0] = numsVat[indexLeft].id;
            returnSum[1] = numsVat[indexRight].id;
            break;
        }
        else if( target < (numsVat[indexLeft].value + numsVat[indexRight].value)) 
        {
            //大于了目标 target；
            indexRight--;
        }
        else
        {
            //小于了目标 target；
            indexLeft++;
        }
    }
    return returnSum;
}


int main()
{
    int arr[] = {3, 3};
    int return_size = 0;
    int *ret = qtwoSum(arr, 2, 6, &return_size);
    for (int i = 0; i < return_size; i++) {
        printf("%d ", ret[i]);
    }
    printf("\n");
    free(ret);
    return 0;
}